//题目：
// 给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
// 现在，我们定义一种 跟随 关系，当且仅当 b > c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。
// 我们用这种形式来构造 数对链 。找出并返回能够形成的 最长数对链的长度 。
// 你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
    struct compare
    {
        bool operator()(const vector<int>& nums1,const vector<int>& nums2)
        {
            return nums1[0]<nums2[0];
        }
    };
public:
    int findLongestChain(vector<vector<int>>& nums) 
    {
        if(nums.size()==1) return 1;

        //对nums中的元素，按nums[0]排升序
        sort(nums.begin(),nums.end(),compare());

        //1.创建dp表————dp[i]表示从初始位置到nums[i]的 最长数对链的长度
        vector<int> dp(nums.size(),1);
        //2.初始化
        //3.填表————动态转移方程：dp[i]=nums[i][0]>nums[i-1][1]?dp[i-1]+1:dp[i-1];
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i][0]>nums[j][1])
                {
                    dp[i]=dp[j]+1;
                    break;
                }
            }
        }
        //4.确定返回值
        int ret=1;
        for(int i=0;i<nums.size();i++)
            ret=max(ret,dp[i]);
        return ret;
    }
};